<?php
/**
 * AVL树：保持平衡的二叉搜索树
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbBinaryTreeInterface;

class AVLTree implements XxbBinaryTreeInterface
{
    /**
     * 根结点
     * @var BalanceBinaryTreeNode|null
     */
    private $root;

    /**
     * @return BalanceBinaryTreeNode|null
     */
    public function getRoot()
    {
        return $this->root;
    }

    /**
     * @param BalanceBinaryTreeNode|null $root
     */
    public function setRoot($root)
    {
        $this->root = $root;
    }

    /**
     * 结点个数
     * @var int
     */
    private $size;

    public function __construct()
    {
        $this->root = null;
        $this->size = 0;
    }

    public function isEmpty()
    {
        return $this->size == 0;
    }

    public function getSize()
    {
        return $this->size;
    }

    public function add($value)
    {
        //$this->setRoot($this->addNode($this->root, $value));
        $this->setRoot($this->recurseAddNode($this->root, $value));
    }

    private function loopAddNode()
    {

    }

    /**
     * 通过递归的方式添加结点：
     * 与当前结点进行比较，比它大，则继续到右子树找；比它小，则继续到左子树找；相等的不处理
     * 找到一个空的结点，则在该处添加新结点
     *
     * 平衡问题：
     * 由于添加了叶子节点，可能会增加树的高度，从而导致不平衡
     * 添加位置可能在不平衡结点左边的左边、右边的右边、左边的右边或者右边的左边
     * 解决办法就是对不平衡结点进行旋转，旋转成新插入结点的兄弟结点，以减低左或者右子树的高度，达到再次平衡
     * @param BalanceBinaryTreeNode|null $node
     * @param $value
     *
     * @return BalanceBinaryTreeNode|null
     */
    private function recurseAddNode($node, $value)
    {
        if (is_null($node)) {
            $this->size++;
            return new BalanceBinaryTreeNode($value);
        }

        if ($value > $node->getValue()) {
            $rightNode = $this->recurseAddNode($node->getRight(), $value);
            $node->setRight($rightNode);
        } elseif ($value < $node->getValue()) {
            $leftNode = $this->recurseAddNode($node->getLeft(), $value);
            $node->setLeft($leftNode);
        }

        // 结点的高度
        $this->setNodeHeight($node);
        // 树的平衡
        $factor = $this->getFactor($node);
        if ($factor > 1 && $this->getFactor($node->getLeft()) >= 0) {
            // 往结点的左边的左边加入叶子结点
            $node = $this->rightRotate($node);
        } else if ($factor < -1 && $this->getFactor($node->getRight()) < 0) {
            // 往该结点的右边的右边插入叶子结点
            $node = $this->leftRotate($node);
        } else if ($factor > 1 && $this->getFactor($node->getLeft()) < 0) {
            // 往该结点的左边的右边插入叶子结点
            $node->setLeft($this->leftRotate($node->getLeft()));
            $node = $this->rightRotate($node);
        } else if ($factor < -1 && $this->getFactor($node->getRight()) > 0) {
            // 往该结点的右边的左边插入叶子结点
            $node->setRight($this->rightRotate($node->getRight()));
            $node = $this->leftRotate($node);
        }

        return $node;
    }

    public function shift($value)
    {
        // TODO: Implement shift() method.
    }

    public function previousTraversal()
    {
        return $this->previousTraversalNodes($this->root);
    }

    /**
     * 通过递归的方式前序遍历
     * @param BalanceBinaryTreeNode|null $node
     * @param array                 $result
     *
     * @return array|mixed
     */
    private function previousTraversalNodes($node, &$result = [])
    {
        if (is_null($node)) {
            return $result;
        }
        $result[] = $node->getValue();
        $this->previousTraversalNodes($node->getLeft(), $result);
        $this->previousTraversalNodes($node->getRight(), $result);
        return $result;
    }

    public function middleTraversal()
    {
        return $this->middleTraversalNodes($this->root);
    }

    /**
     * 递归实现中序遍历
     * @param BalanceBinaryTreeNode|null $node
     * @param array                 $result
     *
     * @return array|mixed
     */
    private function middleTraversalNodes($node, &$result = [])
    {
        if (is_null($node)) {
            return $result;
        }
        $this->middleTraversalNodes($node->getLeft(), $result);
        $result[] = $node->getValue();
        $this->middleTraversalNodes($node->getRight(), $result);
        return $result;
    }

    public function afterTraversal()
    {
        return $this->afterTraversalNodes($this->root);
    }

    /**
     * 递归实现后序遍历
     * @param BalanceBinaryTreeNode|null $node
     * @param array                 $result
     *
     * @return array|mixed
     */
    private function afterTraversalNodes($node, &$result = [])
    {
        if (is_null($node)) {
            return $result;
        }
        $this->afterTraversalNodes($node->getLeft(), $result);
        $this->afterTraversalNodes($node->getRight(), $result);
        $result[] = $node->getValue();
        return $result;
    }

    /**
     * 通过队列进行层级遍历
     * 按层进行遍历，每层又从左到右遍历
     * @return array
     */
    public function hierarchicalTraversal()
    {
        if (empty($this->root)) {
            return [];
        }

        $result = [];
        $queue = new \SplQueue();
        $queue->push($this->root);
        while (!$queue->isEmpty()) {
            /** @var $node BalanceBinaryTreeNode */
            $node = $queue->shift();
            $result[] = $node->getValue();
            !is_null($node->getLeft()) && $queue->push($node->getLeft());
            !is_null($node->getRight()) && $queue->push($node->getRight());
        }

        return $result;
    }

    public function search($value)
    {
        // TODO: Implement search() method.
    }

    public function searchParent($value)
    {
        // TODO: Implement searchParent() method.
    }

    /**
     * 是不是一棵二叉搜索树
     * @return bool
     */
    public function isSearch()
    {
        $result = $this->middleTraversal();
        for ($i=1; $i<$this->size; $i++) {
            if ($result[$i] < $result[$i-1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 检查二叉树是否平衡
     * @param BalanceBinaryTreeNode|null $root
     * @return bool
     */
    public function isBalance($root = null)
    {
        return $this->checkBalance(is_null($root) ? $this->root : $root);
    }

    /**
     * 通过递归的方式，查看每一个结点的平衡因子绝对值是否<=1
     * @param BalanceBinaryTreeNode|null $node
     *
     * @return bool
     */
    private function checkBalance($node)
    {
        if (is_null($node)) {
            // 叶子结点的子结点(即一个空结点)
            return true;
        }

        if (abs($this->getFactor($node)) > 1) {
            // 结点的平衡因子的绝对值大于1 则是不平衡
            return false;
        }

        return $this->checkBalance($node->getLeft()) && $this->checkBalance($node->getRight());
    }

    /**
     * 获取指定结点的平衡因子
     * 结点的平衡因子=左子树的高度-右子树的高度
     * @param BalanceBinaryTreeNode|null $node
     *
     * @return int
     */
    private function getFactor($node)
    {
        if (is_null($node)) {
            // 假设空结点的平衡因子就是0
            return 0;
        }

        $leftNodeHeight = is_null($node->getLeft()) ? 0 : $node->getLeft()->getHeight();
        $rightNodeHeight = is_null($node->getRight()) ? 0 : $node->getRight()->getHeight();
        return $leftNodeHeight - $rightNodeHeight;
    }

    /**
     * 往结点的右边的右边添加结点导致不平衡
     * 旋转该不平衡结点到新加入结点的左边
     *        nb(不平衡结点)                                 r
     *      /   \                                        /  \
     *    T1     r                   =>                nb    new
     *         /   \                                  /  \
     *       T2     new                             T1   T2
     * @param BalanceBinaryTreeNode|null $node
     *
     * @return false|BalanceBinaryTreeNode
     */
    private function leftRotate($node)
    {
        $rightChild = $node->getRight();
        if (is_null($rightChild)) {
            return false;
        }

        $node->setRight($rightChild->getLeft());
        $rightChild->setLeft($node);
        $this->setNodeHeight($node);
        $this->setNodeHeight($rightChild);
        return $rightChild;
    }

    /**
     * 设置结点高度
     * @param BalanceBinaryTreeNode $node
     */
    private function setNodeHeight(BalanceBinaryTreeNode $node)
    {
        // 维护结点的高度
        $leftNodeHeight = is_null($node->getLeft()) ? 0 : $node->getLeft()->getHeight();
        $rightNodeHeight = is_null($node->getRight()) ? 0 : $node->getRight()->getHeight();
        $node->setHeight(max($leftNodeHeight, $rightNodeHeight) + 1);
    }

    /**
     * 往结点的左边的左边添加结点导致不平衡
     * 旋转该不平衡结点到新加入结点的右边
     *           nb(不平衡结点)                     r
     *         /   \                            /  \
     *        r     T2                =>      new  nb
     *      /   \                                  /  \
     *     new   T1                              T1   T2
     * @param BalanceBinaryTreeNode|null $node
     *
     * @return false|BalanceBinaryTreeNode
     */
    private function rightRotate(BalanceBinaryTreeNode $node)
    {
        $leftChild = $node->getLeft();
        $node->setLeft($leftChild->getRight());
        $leftChild->setRight($node);
        $this->setNodeHeight($node);
        $this->setNodeHeight($leftChild);
        return $leftChild;
    }
}
